<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>增量包算法</title>
</head>
<style>
  .container{
    width: 1000px;
    margin: 0 auto;
  }
  .item{
    margin-bottom: 20px;
    vertical-align: middle;
    float: none;
    clear: both;
  }
  .item label{
    width: 100px;
    float: left;
  }
  .item textarea{
    width: 60%;
    min-height: 100px;
  }
</style>
<script>
  //压缩增量包
  function MinChunk(chunkArr,s1) {
    var minChunk=[]
    for(let i=0;i<chunkArr.length;i++){
      let arr=chunkArr[i];
      if(arr[0]==='e'&&arr[2]<String(arr[1]).length+String(arr[2]).length){
        arr=['a',s1.substr(arr[1],arr[2])]
      }
      var lastArr=minChunk[minChunk.length-1];
      if(arr[0]==='a'&&lastArr&&lastArr[0]==='a'){
        lastArr[1]=lastArr[1]+arr[1];
      }else{
        minChunk.push(arr)
      }
    }
    const narr=[]
    for(let i=0;i<minChunk.length;i++){
      let arr=minChunk[i];
      if(arr[0]==='a'){
        narr.push(arr[1])
      }else if(arr[0]==='e'){
        narr.push([arr[1],arr[2]])
      }
    }
    return narr;
  }

  //比较两字符的相等长度和大小
  function compareLen(n1,n2,str1,str2) {
    //求出相等部分
    var len=0;
    while (n1+len<=str1.length&&n2+len<=str2.length&&str1.charCodeAt(n1+len)===str2.charCodeAt(n2+len)){
      len++;
    }
    var code1=str1.charCodeAt(n1+len);
    var code2=str2.charCodeAt(n2+len);

    if(Number.isNaN(code1)&&Number.isNaN(code2)){
      return [len,0]
    }else if(Number.isNaN(code1)){
      return [len,-1]
    }else if(Number.isNaN(code2)){
      return [len,1]
    }else{
      //求出大小
      var dis=0;
      if(code1<code2){
        dis=-1
      }else if(code1>code2){
        dis=1
      }
      if(str1.substr(n1,len)!==str2.substr(n2,len)){
        console.log(dis,len,str1.substr(n1,len),'===',str2.substr(n2,len),n1,n2,str1.length,str2.length)
      }

      return [len,dis];
    }
  }

  //查找字符在数组的最大相等长度和大小
  function findLen(str,hasSortArr,callback) {
    var l=0,r=hasSortArr.length;
    var lock=-1;
    var len1=0,len2=0;
    var len=0,dis=0;

    if(hasSortArr.length>0){
      [len1,dis]=callback(str,hasSortArr[0]);
      if(dis<1){
        return [0,len1,dis]
      }
      [len2,dis]=callback(str,hasSortArr[r-1]);
      if(dis>-1){
        return [r-1,len2,dis]
      }
      while(lock===-1){
        var m=(l+r+1)>>1;
        //比较下坐标大小
        [len,dis]=callback(str,hasSortArr[m])
        if(dis===1){
          if(m+1===r){
            if(len<len2){
              lock=r;
              len=len2;
              dis=-1
            }else{
              lock=m;
            }
          }else{
            len1=len;
            l=m
          }
        }else if(dis===-1){
          if(l+1===m){
            if(len<len1){
              lock=l;
              len=len1;
              dis=1
            }else{
              lock=m;
            }
          }else{
            len2=len;
            r=m
          }
        }else{
          lock=m;
        }
      }
      return [lock,len,dis]
    }
    return [lock,0,1]
  }

  //SA[i]表示排名为i的后缀下标、rk[i]表示起始位置的下标为i的后缀的排名
  function getSa(str) {
    var sLen=str.length;//总共排名长度
    //后缀数组
    var sa=[];
    for(var i=0;i<sLen;i++){
      var [n,len,dis]=findLen(i,sa,function (n1,n2) {
        return compareLen(n1,n2,str,str)
      })
      if(dis===1){
        sa.splice(n+1,0,i)
      }else{
        sa.splice(n,0,i)
      }

    }
    return sa
  }
  //用后缀数组，求两个字符的公共子串,也就是两个文件的公共部分
  function makeChunk(s1,s2){
    var sa1=getSa(s1);//后缀数组，排序
    const chunkArr=[]
    let i=0;
    while (i<s2.length){
      var [n,len,dis]=findLen(i,sa1,function (n2,n1) {
        return compareLen(n2,n1,s2,s1)
      })
      if(len>0){
        chunkArr.push(['e',sa1[n],len])
        i=i+len;
      }else{
        chunkArr.push(['a',s2[i]])
        i++
      }
    }
    return chunkArr;
  }

  //执行增量包
  function execChunk(s1,chunk){
    var ns='';
    for(var i=0;i<chunk.length;i++){
      var arr=chunk[i];
      if(Object.prototype.toString.call(arr)==='[object Array]'){
        ns=ns+s1.substr(arr[0],arr[1])
      }else{
        ns=ns+arr
      }
    }
    return ns;
  }
</script>
<script>
  function s1makeChunk() {
    var s1=document.getElementById('s1').value;
    var s2=document.getElementById('s2').value;
    var chunk=makeChunk(s1,s2)
    var cstr=JSON.stringify(chunk)
    document.getElementById('chunk').value=cstr;

    var chunk2=MinChunk(chunk,s1)
    var cstr2=JSON.stringify(chunk2)
    document.getElementById('chunk2').value=cstr2
    return cstr
  }
  function s1execChunk() {
    var s1=document.getElementById('s1').value;
    var s2=document.getElementById('s2').value;
    var cstr=document.getElementById('chunk2').value
    if(!cstr){
      cstr=s1makeChunk();
    }
    var chunk=JSON.parse(cstr)
    var ns=execChunk(s1,chunk)
    document.getElementById('result').innerText='结果为'+(ns===s2);
    document.getElementById('ns').value=ns;
  }
</script>
<body>

<div class="container">
  <div class="item">
    增量包算法:时间复杂度 2*n ~ 2*n阶和 之间
  </div>
  <div class="item">
    <label>输入字符s1：</label> <textarea id="s1">ill:"071b136b",test:"acf98235",wlh_audit_ok:"0cfbdb93",wl</textarea>
  </div>
  <div class="item">
    <label>输入字符s2：</label> <textarea id='s2'>ill:"acf98235",test:"0cfbdb93",wlh_audit_ok:"0cfbdb93",wl</textarea>
  </div>
  <div class="item">
    <label>s1-->s2：</label> <textarea id='chunk'></textarea>
  </div>
  <div class="item">
    <label>指令压缩后</label> <textarea id='chunk2'></textarea><button onClick="s1makeChunk()">生产增量包：</button>
  </div>
  <div class="item">
    <label>结果：</label> <textarea id="ns"></textarea><button onClick="s1execChunk()">执行增量包：</button>
  </div>
  <div id="result"></div>
</div>

</body>
</html>
